package leetcode.LinkedList;

/**
 * @author MaoLin Wang
 * @date 2020/2/110:51
 */
public class _61RotateRight {
    /**
     * 1.先闭塞成环
     * 2.找打原头节点的新位置  (1+k)%length  1是原head的位置
     * 3. 计算新的尾节点距离原头节点的新位置
     * 4.从head开始寻找新的尾节点，则新头节点为该尾节点的下一个，断开该尾节点，返回新头节点
     * @param head
     * @param k
     * @return
     */
    public static ListNode rotateRight(ListNode head, int k) {
        if (head==null){
            return head;
        }
        if (head.next==null){
            return head;
        }
        int length = 0;
        ListNode temp = head;
        while (temp.next!= head) {
            length++;
            if (temp.next==null){
                temp.next=head;
            }else {
                temp = temp.next;
            }
        }
        //旧头节点的新位置
        int newposition=(1+k)%length;
        //计算新尾节点的位置在该位置的右边多少个
        newposition=length-newposition;
        int n;
        temp=head;

        for (n=0; n <newposition ; n++) {
            temp=temp.next;
        }
        ListNode newHead=temp.next;
        temp.next=null;

        return newHead;
    }

    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.next=new ListNode(2);
        l1.next.next=new ListNode(3);
        l1.next.next.next=new ListNode(4);
        ListNode node = rotateRight(l1, 2);
        ListNode.printNode(node);
    }

}
